/*
 * @lc app=leetcode.cn id=416 lang=cpp
 *
 * [416] 分割等和子集
 *
 * 方法1（官方题解）：0-1背包问题
 * - 状态 dp[i][j]：是否存在一种选取方案
 *   + 从数组的 [0,i] 下标范围内选取若干个正整数（可以是0个）
 *   + 被选取的正整数的和等于 j
 * - 状态转移方程：dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]
 *   + 选取 nums[i]：dp[i-1][j-nums[i]]
 *   + 不选取 nums[i]：dp[i-1][j]
 *
 * 方法2（官方题解）：优化方法1 - 每一行的dp值都只与上一行的dp值有关
 * - 状态转移方程：dp[j] = dp[j] | dp[j−nums[i]]
 *   + 选取 nums[i]：dp[j] 的旧值
 *   + 不选取 nums[i]：dp[j−nums[i]] 的旧值
 * - 第二层的循环需要从大到小计算：防止在计算dp[j]值的时候，dp[j−nums[i]]已经被更新过
 */

#include <vector>
#include <iostream>

// @lc code=start
class Solution
{
public:
    bool canPartition_00(std::vector<int> &nums)
    {
        const int len = nums.size();

        int max_num = 0;
        int sum = 0;
        for (auto n : nums)
        {
            sum += n;
            if (n > max_num)
                max_num = n;
        }
        if (sum & 1) // 只包含正整数
            return false;

        int half = sum / 2;
        if (max_num > half)
            return false;
        else if (max_num == half)
            return true;

        std::vector<std::vector<int>> dp(len, std::vector(half + 1, 0));
        for (int i = 0; i < len; i++)
            dp[i][0] = true;
        dp[0][nums[0]] = true;

        for (int i = 1; i < len; i++)
        {
            int num = nums[i];
            for (int j = 0; j <= half; j++)
            {
                if (j >= num)
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }

        return dp[len - 1][half];
    }

    bool canPartition_01(std::vector<int> &nums)
    {
        int max_num = 0;
        int sum = 0;
        for (auto n : nums)
        {
            sum += n;
            if (n > max_num)
                max_num = n;
        }
        if (sum & 1) // 只包含正整数
            return false;

        int half = sum / 2;
        if (max_num > half)
            return false;
        else if (max_num == half)
            return true;

        std::vector<int> dp(half + 1);
        dp[0] = true;
        for (auto num : nums)
        {
            for (int j = half; j >= num; j--)
                dp[j] |= dp[j - num];
        }

        return dp[half];
    }
};
// @lc code=end
